/*
前缀树，实现动态路由用的辅助数据结构
下边的代码其实就是在建树，只不过比较复杂
*/

package gee

import "strings"

type node struct {
	pattern  string // 这个其实是用来标识找到完整路由了
	part     string
	children []*node
	isWild   bool // 是否精确匹配，这是进行模糊匹配的核心
}

// 给insert的辅助函数，匹配到表示已经创建此节点，没有则会insert新节点
func (n *node) matchChild(part string) *node {
	for _, child := range n.children {
		if child.part == part || child.isWild {
			return child
		}
	}
	return nil
}

// 给search的辅助函数，所有匹配到的节点均要返回
func (n *node) matchChildren(part string) []*node {
	nodes := make([]*node, 0)
	for _, child := range n.children {
		if child.part == part || child.isWild { //如果碰到模糊匹配那就
			nodes = append(nodes, child)
		}
	}
	return nodes
}

func (n *node) insert(pattern string, parts []string, height int) {
	// 递归终止，赋值给node完整的pattern，有pattern就表示此路由匹配完整
	if len(parts) == height {
		n.pattern = pattern
		return
	}

	part := parts[height]
	// 如果没匹配到就插入新节点，然后保存到n.children中
	child := n.matchChild(part)
	if child == nil {
		child = &node{
			part:   part,
			isWild: part[0] == '*' || part[0] == ':',
		}
		n.children = append(n.children, child)
	}
	// 孩子节点插入下一层节点
	child.insert(pattern, parts, height+1)
}

// 这里输入的parts是真实的路由
func (n *node) search(parts []string, height int) *node {
	// 如果有"*"那这条路由到这就已经完整了
	if len(parts) == height || strings.HasPrefix(n.part, "*") {
		// 检查路由是否完整
		if n.pattern == "" {
			return nil
		}
		return n
	}

	part := parts[height]
	// 在注册路由建好的树中进行匹配
	children := n.matchChildren(part)
	for _, child := range children {
		// 匹配到了就返回，否则遍历下一个
		if res := child.search(parts, height+1); res != nil {
			return res
		}
	}
	return nil
}
